package leetcode.year2021.month11;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
// 234. 回文链表
public class _04_3IsPalindrome234 {
  public boolean isPalindrome(ListNode head) {
    // 方法二： 时间复杂度为O（n）,空间复杂度为O（1） 快慢指针，找到中点, 反转后部分链表，比较
    if (head == null || head.next == null){
      return true;
    }
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode slow = dummy;
    ListNode fast = dummy;

    while (fast != null && fast.next != null){
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode rightListNode = slow.next;
    slow.next = null;

    rightListNode = revertListNode(rightListNode);

    ListNode rightPoint = rightListNode;
    ListNode leftPoint = head;

    while (rightPoint != null){
      if (rightPoint.val != leftPoint.val){
        revertListNode(rightListNode);
        slow.next = rightListNode;
        return false;
      }
      rightPoint = rightPoint.next;
      leftPoint = leftPoint.next;
    }

    return true;

//    // 方法一： 使用数组存储值，然后双指针查找
//    ArrayList<ListNode> nodeList = new ArrayList<>();
//
//    ListNode prev = head;
//    while (prev != null){
//      nodeList.add(prev);
//      prev = prev.next;
//    }
//
//    int left = 0;
//    int right = nodeList.size() -1;
//    while (left < right){
//      if (nodeList.get(left).val != nodeList.get(right).val){
//        return false;
//      }
//      left++;
//      right--;
//    }
//    return true;
  }

  public ListNode revertListNode(ListNode head){
    if (head == null || head.next == null){
      return head;
    }
    ListNode next = head.next;
    head.next = null;

    while (next != null){
      ListNode temp = next.next;
      next.next = head;
      head = next;
      next = temp;
    }
    return head;
//     if (head == null || head.next == null){
//       return head;
//     }
//
//     ListNode next = head.next;
//     head.next = null;
//
//     while (next != null) {
//       ListNode tempNext = next.next;
//       next.next = head;
//       head = next;
//       next = tempNext;
//     }
//
//     return head;


//    if (head == null || head.next == null){
//      return head;
//    }
//    ListNode ans = null;
//    ListNode prev = head;
//    ListNode next = head.next;
//    while (next != null){
//      prev.next = ans;
//      ans = prev;
//      prev = next;
//      next = next.next;
//    }
//    prev.next = ans;
//    return prev;
  }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


  /**
   * 234. 回文链表
   * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
   *
   *
   *
   * 示例 1：
   *
   *
   * 输入：head = [1,2,2,1]
   * 输出：true
   * 示例 2：
   *
   *
   * 输入：head = [1,2]
   * 输出：false
   *
   *
   * 提示：
   *
   * 链表中节点数目在范围[1, 105] 内
   * 0 <= Node.val <= 9
   *
   *
   * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
   */
}
